#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1080. 根到叶路径上的不足节点
// 【难度】中等
// 【提交】2025.10.16 https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/submissions/671190355/
// 【标签】树；深度优先搜索；二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if(root->left == nullptr && root->right == nullptr) {
            if(root->val < limit) return nullptr;
            else return root;
        }
        if(root->left != nullptr) {
            root->left = sufficientSubset(root->left, limit - root->val);
        }
        if(root->right != nullptr) {
            root->right = sufficientSubset(root->right, limit - root->val);
        }
        if(root->left == nullptr && root->right == nullptr) return nullptr;
        else return root;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定二叉树的根节点root和整数limit，删除所有不足节点。
 * 不足节点定义：如果从根节点到该节点的每条路径的和都严格小于limit，则该节点为不足节点。
 * 模型：树形结构+深度优先搜索，通过后序遍历判断和删除不足节点。
 * 
 * 二、标准解法状态设计
 * 1. 使用深度优先搜索遍历二叉树。
 * 2. 对于叶子节点，直接判断节点值是否小于limit。
 * 3. 对于非叶子节点，递归处理左右子树，并将limit减去当前节点值。
 * 4. 如果处理后的左右子树都为空，说明所有路径都不满足条件，删除当前节点。
 * 
 * 三、你的实现思路
 * 使用递归DFS，在遍历过程中判断节点是否为不足节点。
 * 通过后序遍历，先处理子节点再处理父节点，确保正确删除不足节点。
 * 
 * 四、逐行注释（带细节提醒）
 * if(root->left == nullptr && root->right == nullptr) { // 叶子节点处理
 *     if(root->val < limit) return nullptr; // 路径和不足，删除节点
 *     else return root; // 路径和足够，保留节点
 * }
 * 
 * if(root->left != nullptr) { // 递归处理左子树
 *     root->left = sufficientSubset(root->left, limit - root->val);
 * }
 * 
 * if(root->right != nullptr) { // 递归处理右子树
 *     root->right = sufficientSubset(root->right, limit - root->val);
 * }
 * 
 * if(root->left == nullptr && root->right == nullptr) return nullptr; // 左右子树都被删除，删除当前节点
 * else return root; // 至少有一个子树存在，保留当前节点
 * 
 * 五、正确性证明
 * 算法通过后序遍历遍历整棵树：
 * 1. 对于叶子节点：直接判断从根到该叶子的路径和是否小于limit
 * 2. 对于非叶子节点：只有当所有子路径（通过左右子树）都不满足条件时，才删除当前节点
 * 3. 通过递归将limit减去当前节点值，确保正确计算剩余需要的路径和
 * 由于DFS会访问所有节点，且每个节点都进行了正确的判断，因此算法正确。
 * 
 * 六、复杂度
 * 时间：O(n)，每个节点只被访问一次。
 * 空间：O(h)，递归栈深度为树的高度。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需一次DFS遍历；
 *   - 代码简洁，逻辑清晰；
 *   - 准确判断和删除不足节点。
 * 缺点：
 *   - 递归深度可能受树高度限制；
 *   - 修改了原始树结构。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (root == nullptr) return nullptr;
 * 2. 可以使用迭代DFS避免递归深度问题；
 * 3. 对于教学场景，可以添加注释解释为什么需要后序遍历。
 * 
 * 九、一句话总结
 * 通过深度优先搜索和后序遍历判断路径和，你的实现准确地删除了所有不足节点，
 * 展现了树形结构问题中递归思想的精妙应用。
 */